SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Banker's algorithm</title>

</head>

Banker's algorithm

</h1>

</header>

Banker's algorithm is a <a href="Resource_allocation" title="Resource allocation">resource allocation</a> and <a href="Deadlock_(computer_science)" title="Deadlock (computer science)">deadlock</a> avoidance <a href="Algorithm" title="Algorithm">algorithm</a> developed by <a href="Edsger_Dijkstra" class="mw-redirect" title="Edsger Dijkstra">Edsger Dijkstra</a> that tests for safety by simulating the allocation of predetermined maximum possible amounts of all <a href="Resource_(computer_science)" class="mw-redirect" title="Resource (computer science)">resources</a>, and then makes an "s-state" check to test for possible deadlock conditions for all other pending activities, before deciding whether allocation should be allowed to continue.

The algorithm was developed in the design process for the <a href="THE_(operating_system)" class="mw-redirect" title="THE (operating system)">THE operating system</a> and originally described (in <a href="Dutch_language" title="Dutch language">Dutch</a>) in EWD108.<a href="#cite_note-1">[1]</a> When a new process enters a system, it must declare the maximum number of instances of each resource type that it may ever claim; clearly, that number may not exceed the total number of resources in the system. Also, when a process gets all its requested resources it must return them in a finite amount of time.

<div class="mw-heading mw-heading2"><h2 id="Resources">Resources</h2></div>

For the Banker's algorithm to work, it needs to know three things:

<ul><li>How much of each resource each process could possibly request ("MAX")</li>

<li>How much of each resource each process is currently holding ("ALLOCATED")</li>

<li>How much of each resource the system currently has available ("AVAILABLE")</li></ul>

Resources may be allocated to a process only if the amount of resources requested is less than or equal to the amount available; otherwise, the process waits until resources are available.

Some of the resources that are tracked in real systems are <a href="Memory_(computers)" class="mw-redirect" title="Memory (computers)">memory</a>, <a href="Semaphore_(programming)" title="Semaphore (programming)">semaphores</a> and <a href="Interface_(computer_science)" class="mw-redirect" title="Interface (computer science)">interface</a> access.

The Banker's algorithm derives its name from the fact that this algorithm could be used in a banking system to ensure that the bank does not run out of resources, because the bank would never allocate its money in such a way that it can no longer satisfy the needs of all its customers.<a href="#cite_note-2">[2]</a> By using the Banker's algorithm, the bank ensures that when customers request money the bank never leaves a safe state. If the customer's request does not cause the bank to leave a safe state, the cash will be allocated, otherwise the customer must wait until some other customer deposits enough.

Basic data structures to be maintained to implement the Banker's algorithm:

Let n be the number of processes in the system and m be the number of resource types. Then we need the following data structures:

<ul><li>Available: A vector of length m indicates the number of available resources of each type. If Available[j] = k, there are k instances of resource type Rj available.</li>

<li>Max: An n × m matrix defines the maximum demand of each process. If Max[i,j] = k, then Pi may request at most k instances of resource type Rj.</li>

<li>Allocation: An n × m matrix defines the number of resources of each type currently allocated to each process. If Allocation[i,j] = k, then process Pi is currently allocated k instances of resource type Rj.</li>

<li>Need: An n × m matrix indicates the remaining resource need of each process. If Need[i,j] = k, then Pi may need k more instances of resource type Rj to complete the task.</li></ul>

Note: Need[i,j] = Max[i,j] - Allocation[i,j].

n=m-a.

<div class="mw-heading mw-heading3"><h3 id="Example">Example</h3></div>

<caption>Total system resources

</caption>

<th>A

</th>

<th>B

</th>

<th>C

</th>

<th>D

</th></tr>

<tr>

<td>6

</td>

<td>5

</td>

<td>7

</td>

<td>6

</td></tr></tbody></table>

<caption>Available system resources

</caption>

<th>A

</th>

<th>B

</th>

<th>C

</th>

<th>D

</th></tr>

<tr>

<td>3

</td>

<td>1

</td>

<td>1

</td>

<td>2

</td></tr></tbody></table>

<caption>Processes (currently allocated resources)

</caption>

<th>

</th>

<th>A

</th>

<th>B

</th>

<th>C

</th>

<th>D

</th></tr>

<tr>

<th>P1

</th>

<td>1

</td>

<td>2

</td>

<td>2

</td>

<td>1

</td></tr>

<tr>

<th>P2

</th>

<td>1

</td>

<td>0

</td>

<td>3

</td>

<td>3

</td></tr>

<tr>

<th>P3

</th>

<td>1

</td>

<td>2

</td>

<td>1

</td>

<td>0

</td></tr></tbody></table>

<caption>Processes (maximum resources)

</caption>

<th>

</th>

<th>A

</th>

<th>B

</th>

<th>C

</th>

<th>D

</th></tr>

<tr>

<th>P1

</th>

<td>3

</td>

<td>3

</td>

<td>2

</td>

<td>2

</td></tr>

<tr>

<th>P2

</th>

<td>1

</td>

<td>2

</td>

<td>3

</td>

<td>4

</td></tr>

<tr>

<th>P3

</th>

<td>1

</td>

<td>3

</td>

<td>5

</td>

<td>0

</td></tr></tbody></table>

<pre>Need = maximum resources - currently allocated resources

</pre>

<caption>Processes (possibly needed resources)

</caption>

<th>

</th>

<th>A

</th>

<th>B

</th>

<th>C

</th>

<th>D

</th></tr>

<tr>

<th>P1

</th>

<td>2

</td>

<td>1

</td>

<td>0

</td>

<td>1

</td></tr>

<tr>

<th>P2

</th>

<td>0

</td>

<td>2

</td>

<td>0

</td>

<td>1

</td></tr>

<tr>

<th>P3

</th>

<td>0

</td>

<td>1

</td>

<td>4

</td>

<td>0

</td></tr></tbody></table>

<div class="mw-heading mw-heading3"><h3 id="Safe_and_unsafe_states">Safe and unsafe states</h3></div>

A state (as in the above example) is considered safe if it is possible for all processes to finish executing (terminate). Since the system cannot know when a process will terminate, or how many resources it will have requested by then, the system assumes that all processes will eventually attempt to acquire their stated maximum resources and terminate soon afterward. This is a reasonable assumption in most cases since the system is not particularly concerned with how long each process runs (at least not from a deadlock avoidance perspective). Also, if a process terminates without acquiring its maximum resource it only makes it easier on the system.

A safe state is considered to be the decision maker if it's going to process ready queue.

Given that assumption, the algorithm determines if a state is safe by trying to find a hypothetical set of requests by the processes that would allow each to acquire its maximum resources and then terminate (returning its resources to the system). Any state where no such set exists is an unsafe state.

We can show that the state given in the previous example is a safe state by showing that it is possible for each process to acquire its maximum resources and then terminate.

<ol><li>P1 needs 2 A, 1 B and 1 D more resources, achieving its maximum

<ul><li>[available resource: ⟨3 1 1 2⟩ − ⟨2 1 0 1⟩ = ⟨1 0 1 1⟩]</li>

<li>The system now still has 1 A, no B, 1 C and 1 D resource available</li></ul></li>

<li>P1 terminates, returning 3 A, 3 B, 2 C and 2 D resources to the system

<ul><li>[available resource: ⟨1 0 1 1⟩ + ⟨3 3 2 2⟩ = ⟨4 3 3 3⟩]</li>

<li>The system now has 4 A, 3 B, 3 C and 3 D resources available</li></ul></li>

<li>P2 acquires 2 B and 1 D extra resources, then terminates, returning all its resources

<ul><li>[available resource: ⟨4 3 3 3⟩ − ⟨0 2 0 1⟩ + ⟨1 2 3 4⟩ = ⟨5 3 6 6⟩]</li>

<li>The system now has 5 A, 3 B, 6 C and 6 D resources</li></ul></li>

<li>P3 acquires 1 B and 4 C resources and terminates.

<ul><li>[available resource: ⟨5 3 6 6⟩ − ⟨0 1 4 0⟩ + ⟨1 3 5 0⟩ = ⟨6 5 7 6⟩]</li>

<li>The system now has all resources: 6 A, 5 B, 7 C and 6 D</li></ul></li>

<li>Because all processes were able to terminate, this state is safe</li></ol>

For an example of an unsafe state, consider what would happen if process 2 was holding 1 unit of resource B at the beginning.

<div class="mw-heading mw-heading3"><h3 id="Requests">Requests</h3></div>

When the system receives a request for resources, it runs the Banker's algorithm to determine if it is safe to grant the request.

The algorithm is fairly straightforward once the distinction between safe and unsafe states is understood.

<ol><li>Can the request be granted?

<ul><li>If not, the request is impossible and must either be denied or put on a waiting list</li></ul></li>

<li>Assume that the request is granted</li>

<li>Is the new state safe?

<ul><li>If so grant the request</li>

<li>If not, either deny the request or put it on a waiting list</li></ul></li></ol>

Whether the system denies or postpones an impossible or unsafe request is a decision specific to the operating system.

<div class="mw-heading mw-heading4"><h4 id="Example_2">Example</h4></div>

Starting in the same state as the previous example started in, assume process 1 requests 2 units of resource C.

<ol><li>There is not enough of resource C available to grant the request</li>

<li>The request is denied</li></ol>

On the other hand, assume process 3 requests 1 unit of resource C.

<ol><li>There are enough resources to grant the request</li>

<li>Assume the request is granted

<ul><li>The new state of the system would be:</li></ul></li></ol>

<pre> Available system resources

A B C D

Free 3 1 0 2

</pre>

<pre> Processes (currently allocated resources):

A B C D

P1 1 2 2 1

P2 1 0 3 3

P3 1 2 2 0

</pre>

<pre> Processes (maximum resources):

A B C D

P1 3 3 2 2

P2 1 2 3 4

P3 1 3 5 0

</pre>

<ol><li>Determine if this new state is safe

<ol><li>P1 can acquire 2 A, 1 B and 1 D resources and terminate</li>

<li>Then, P2 can acquire 2 B and 1 D resources and terminate</li>

<li>Finally, P3 can acquire 1 B and 3 C resources and terminate</li>

<li>Therefore, this new state is safe</li></ol></li>

<li>Since the new state is safe, grant the request</li></ol>

Final example: from the state we started at, assume that process 2 requests 1 unit of resource B.

<ol><li>There are enough resources</li>

<li>Assuming the request is granted, the new state would be:</li></ol>

<pre> Available system resources:

A B C D

Free 3 0 1 2

</pre>

<pre> Processes (currently allocated resources):

A B C D

P1 1 2 5 1

P2 1 1 3 3

P3 1 2 1 0

</pre>

<pre> Processes (maximum resources):

A B C D

P1 3 3 2 2

P2 1 2 3 4

P3 1 3 5 0

</pre>

<ol><li>Is this state safe? Assuming P1, P2, and P3 request more of resource B and C.

<ul><li>P1 is unable to acquire enough B resources</li>

<li>P2 is unable to acquire enough B resources</li>

<li>P3 is unable to acquire enough B resources</li>

<li>No process can acquire enough resources to terminate, so this state is not safe</li></ul></li>

<li>Since the state is unsafe, deny the request</li></ol>

<div class="mw-highlight mw-highlight-lang-numpy mw-content-ltr" dir="ltr"><pre>import numpy as np

n_processes = int(input("Number of processes? "))

n_resources = int(input("Number of resources? "))

available_resources = [int(x) for x in input("Claim vector? ").split(" ")]

currently_allocated = np.array([

[int(x) for x in input(f"Currently allocated for process {i + 1}? ").split(" ")]

for i in range(n_processes)

])

max_demand = np.array([

[int(x) for x in input(f"Maximum demand from process {i + 1}? ").split(" ")]

for i in range(n_processes)

])

total_available = available_resources - np.sum(currently_allocated, axis=0)

running = np.ones(n_processes) # An array with n_processes 1's to indicate if process is yet to run

while np.count_nonzero(running) > 0:

at_least_one_allocated = False

for p in range(n_processes):

if running[p]:

if all(i >= 0 for i in total_available - (max_demand[p] - currently_allocated[p])):

at_least_one_allocated = True

print(f"{p} is running")

running[p] = 0

total_available += currently_allocated[p]

if not at_least_one_allocated:

print("Unsafe")

break # exit

else:

print("Safe")

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Limitations">Limitations</h2></div>

Like the other algorithms, the Banker's algorithm has some limitations when implemented. Specifically, it needs to know how much of each resource a process could possibly request. In most systems, this information is unavailable, making it impossible to implement the Banker's algorithm. Also, it is unrealistic to assume that the number of processes is static since in most systems the number of processes varies dynamically. Moreover, the requirement that a process will eventually release all its resources (when the process terminates) is sufficient for the correctness of the algorithm, however it is not sufficient for a practical system. Waiting for hours (or even days) for resources to be released is usually not acceptable.

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFDijkstra" class="citation book cs1"><a href="Edsger_W._Dijkstra" title="Edsger W. Dijkstra">Dijkstra, Edsger W.</a> <a rel="nofollow" class="external text" href="http://www.cs.utexas.edu/users/EWD/ewd01xx/EWD108.PDF">Een algorithme ter voorkoming van de dodelijke omarming (EWD-108)</a> (PDF). E.W. Dijkstra Archive. Center for American History, <a href="University_of_Texas_at_Austin" title="University of Texas at Austin">University of Texas at Austin</a>.</cite> (<a rel="nofollow" class="external text" href="http://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD108.html">transcription</a>) (in Dutch; An algorithm for the prevention of the <a href="Deadlock_(computer_science)" title="Deadlock (computer science)">deadly embrace</a>)

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFSilberschatz,_Galvin,_&_Gagne2013" class="citation book cs1">Silberschatz, Galvin, & Gagne (2013). Operating System Concepts, 9th Edition. Wiley. p. 330. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-118-06333-0</bdi>.</cite><code class="cs1-code">{{cite book}}</code>: CS1 maint: multiple names: authors list (link)

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li>"<a rel="nofollow" class="external text" href="https://web.archive.org/web/20101013000653/http://codex.cs.yale.edu/avi/os-book/OS7/os7c/index.html">Operating System Concepts</a>" by Silberschatz, Galvin, and Gagne (pages 259-261 of the 7th edition)</li>

<li>"<a rel="nofollow" class="external text" href="https://web.archive.org/web/20140924121328/http://codex.cs.yale.edu/avi/os-book/OS8/os8c/index.html">Operating System Concepts</a>" by Silberschatz, Galvin, and Gagne (pages 298-300 of the 8th edition)</li>

<li><cite id="CITEREFDijkstra" class="citation book cs1"><a href="Edsger_W._Dijkstra" title="Edsger W. Dijkstra">Dijkstra, Edsger W.</a> <a rel="nofollow" class="external text" href="http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD623.PDF">The mathematics behind the Banker's Algorithm (EWD-623)</a> (PDF). E.W. Dijkstra Archive. Center for American History, <a href="University_of_Texas_at_Austin" title="University of Texas at Austin">University of Texas at Austin</a>.</cite> (<a rel="nofollow" class="external text" href="http://www.cs.utexas.edu/users/EWD/transcriptions/EWD06xx/EWD623.html">transcription</a>) (1977), published as pages 308–312 of Edsger W. Dijkstra, Selected Writings on Computing: A Personal Perspective, Springer-Verlag, 1982. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-90652-5</bdi></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Edsger_Dijkstra318" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="3"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Edsger_Dijkstra318" style="font-size:114%;margin:0 4em"><a href="Edsger_W._Dijkstra" title="Edsger W. Dijkstra">Edsger Dijkstra</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Works</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li>A Primer of ALGOL 60 Programming (book)</li>

<li>Structured Programming (book)</li>

<li>A Discipline of Programming (book)</li>

<li>A Method of Programming (book)</li>

<li>Predicate Calculus and Program Semantics (book)</li>

<li>Selected Writings on Computing: A Personal Perspective (book)</li>

<li>A Note on Two Problems in Connexion with Graphs</li>

<li>Cooperating Sequential Processes</li>

<li>Solution of a Problem in Concurrent Programming Control</li>

<li>The Structure of the 'THE'-Multiprogramming System</li>

<li><a href="Go_To_Statement_Considered_Harmful" class="mw-redirect" title="Go To Statement Considered Harmful">Go To Statement Considered Harmful</a></li>

<li>Notes on Structured Programming</li>

<li>The Humble Programmer</li>

<li>Programming Considered as a Human Activity</li>

<li>How Do We Tell Truths That Might Hurt?</li>

<li>On the Role of Scientific Thought</li>

<li>Self-stabilizing Systems in Spite of Distributed Control</li>

<li><a href="On_the_Cruelty_of_Really_Teaching_Computer_Science" title="On the Cruelty of Really Teaching Computer Science">On the Cruelty of Really Teaching Computer Science</a></li>

<li><a href="Edsger_W._Dijkstra#Selected_publications" title="Edsger W. Dijkstra">Selected papers</a></li>

<li><a href="EWDs" class="mw-redirect" title="EWDs">EWD manuscripts</a></li></ul>

</div></td><td class="noviewer navbox-image" rowspan="3" style="width:1px;padding:0 0 0 2px"><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computer_science#Areas_of_computer_science" title="Computer science">Main research areas</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Theoretical_computer_science" title="Theoretical computer science">Theoretical computing science</a></li>

<li><a href="Software_engineering" title="Software engineering">Software engineering</a></li>

<li><a href="Systems_science" title="Systems science">Systems science</a></li>

<li><a href="Algorithm_design" class="mw-redirect" title="Algorithm design">Algorithm design</a> (<a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra's algorithm</a>)</li>

<li><a href="Concurrent_computing" title="Concurrent computing">Concurrent computing</a></li>

<li><a href="Distributed_computing" title="Distributed computing">Distributed computing</a></li>

<li><a href="Formal_methods" title="Formal methods">Formal methods</a></li>

<li><a href="Programming_methodology" class="mw-redirect" title="Programming methodology">Programming methodology</a></li>

<li><a href="Programming_language_research" class="mw-redirect" title="Programming language research">Programming language research</a></li>

<li><a href="Software_design" title="Software design">Program design</a> and <a href="Software_development" title="Software development">development</a></li>

<li><a href="Software_architecture" title="Software architecture">Software architecture</a></li>

<li><a href="Philosophy_of_computer_science" title="Philosophy of computer science">Philosophy of computer programming and computing science</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related people</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Shlomi_Dolev" title="Shlomi Dolev">Shlomi Dolev</a></li>

<li><a href="Per_Brinch_Hansen" title="Per Brinch Hansen">Per Brinch Hansen</a></li>

<li><a href="Tony_Hoare" title="Tony Hoare">Tony Hoare</a></li>

<li><a href="Ole-Johan_Dahl" title="Ole-Johan Dahl">Ole-Johan Dahl</a></li>

<li><a href="Leslie_Lamport" title="Leslie Lamport">Leslie Lamport</a></li>

<li><a href="David_Parnas" title="David Parnas">David Parnas</a></li>

<li><a href="Jaap_A._Zonneveld" title="Jaap A. Zonneveld">Jaap A. Zonneveld</a></li>

<li><a href="Carel_S._Scholten" title="Carel S. Scholten">Carel S. Scholten</a></li>

<li><a href="Adriaan_van_Wijngaarden" title="Adriaan van Wijngaarden">Adriaan van Wijngaarden</a></li>

<li><a href="Niklaus_Wirth" title="Niklaus Wirth">Niklaus Wirth</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow plainlist" colspan="3"><div>

<ul><li> <a href="https://en.wikiquote.org/wiki/Special:Search/Edsger_W._Dijkstra" class="extiw external" title="wikiquote:Special:Search/Edsger W. Dijkstra">Wikiquote</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-11" href="https://en.wikipedia.org/wiki/?title=Banker's_algorithm&oldid=1295138381">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>